package leetcode;

import java.util.*;

public class Lc133 {

    HashMap<Node, Node> visited = new HashMap<>();

    //深度优先搜索
    public Node cloneGraph22222222(Node node) {
        if (node == null) return node;

        //如果节点已经访问过了，说明已经克隆了，直接返回克隆的node
        if (visited.containsKey(node))
            return visited.get(node);

        //克隆新node
        Node clone = new Node(node.val, new ArrayList<>());
        visited.put(node, clone);

        for (int i = 0; i < node.neighbors.size(); i++) {
            clone.neighbors.add(cloneGraph(node.neighbors.get(i)));
        }
        return clone;
    }





    //广度优先搜索，遍历每个节点，将节点加入队列并保存在map中
    public Node cloneGraph(Node node) {
        if (node == null )
            return node;
        if (node.neighbors == null || node.neighbors.size() == 0) {
            return new Node(node.val, new ArrayList<Node>());
        }
        HashSet<Integer> isVisited = new HashSet<>();
        HashMap<Integer, Node[]> map = new HashMap<>();
        LinkedList<Node> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()) {
            int sz = queue.size();
            while (sz -- > 0) {
                Node temp = queue.poll();
                map.put(temp.val, new Node[]{new Node(temp.val), temp});
                isVisited.add(temp.val);
                for (Node t: temp.neighbors) {
                    if (isVisited.contains(t.val)) continue;
                    queue.offer(t);
                    isVisited.add(t.val);
                }
            }
        }
        Node first = null;
        for (Map.Entry<Integer, Node[]> entry: map.entrySet()) {
            Node n1 = entry.getValue()[0];
            Node n2 = entry.getValue()[1];
            if (n1.val == 1) first = n1;
            ArrayList<Node> list = new ArrayList<>();
            for (int i = 0; i < n2.neighbors.size(); i++) {
                list.add(map.get(n2.neighbors.get(i).val)[0]);
            }
            n1.neighbors = list;
        }
        return first;
    }



}


class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}